Appearance
P1016 [NOIP 1999 普及组/提高组] 旅行家的预算
一、题意转化
汽车从起点开到终点，油箱容量为 (C) 升，每升油可以行驶 (L) 千米。
若两点的距离为 (D)，则这段路需要消耗
[ \frac{D}{L} ]
升油。以后把距离都换成“需要消耗多少升油”，那么：
- 油箱容量是 (C)；
- 从第 (i) 个油站到第 (j) 个油站需要消耗
[ \frac{x_j-x_i}{L} ]
升油；
- 只有消耗量不超过 (C)，才能从一个油站直接开到另一个油站。
另外需要把起点也看成一个油站。
二、贪心做法
对应代码：fanhuitanxin.cpp
2.1 贪心策略
假设当前在油站 (i)，油箱中还剩 (fuel) 升油。
在从 (i) 出发能够到达的所有后续油站中，分两种情况：
存在比当前油站更便宜的油站
找到距离当前油站最近的、油价更低的油站 (j)。
因为 (j) 比 (i) 便宜，在当前油站只需要买到刚好能到达 (j) 的油量。提前购买多余的油不会更优，这部分油完全可以留到 (j) 再买。
不存在比当前油站更便宜的油站
记所有能够到达的油站中油价最低的一个为 (j)。
由于之后经过的油站都不会比当前油站便宜，所以应当把油箱加满，再开到 (j)。
可以把终点也看成一个油价为 (-\infty) 的虚拟油站：
- 如果终点能直接到达，就属于第一种情况，只需要购买刚好到终点的油；
- 如果终点不能直接到达，就不会进入第一种情况。
2.2 为什么最近的低价油站是正确的
假设当前油站 (i) 的价格为 (P_i)，从 (i) 出发能够到达两个价格低于 (P_i) 的油站 (u,v)，且 (u) 更近。
如果先到更远的 (v)，途中一定会经过 (u)。但车完全可以在 (u) 购买同样甚至更少的油。为了到达 (u) 而提前在 (i) 买油更好，因此没有必要跳过更近的 (u)。
所以在所有低价油站中，选择最近的即可。
2.3 为什么“没有更便宜油站时加满”是正确的
当前能够到达的油站价格都不低于 (P_i)。
这些油站中，当前油站的价格最低。若之后要在其他站加油，不可能比现在更便宜；因此在离开当前油站之前，把能提前购买的油加满不会使答案变差。
同时，应当前往其中价格最低的油站，因为这可以在后续购买更少的油。
2.4 复杂度
每个油站最多被扫描常数次，因此时间复杂度为
[ O(N^2) ]
空间复杂度为
[ O(N) ]
在 (N\le 6) 时完全没有压力。
三、动态规划做法
对应代码：dp.cpp
这题中的油量是连续实数，不能直接把“每一升油”作为状态。可以利用价值函数的特殊形状，精确表示所有可能的油量，不需要离散化。
3.1 状态定义
把起点、普通油站按距离排序，并令终点作为最后一个站点。
设汽车到达第 (i) 个实际油站时，油箱中还有 (q) 升油，定义
[ V_i(q) ]
为从该状态开始，最终到达终点所需的最小额外花费。
油量满足
[ 0\le q\le C ]
对于终点，已经到达以后没有额外花费，因此
[ V_{\text{destination}}(q)=0 ]
3.2 状态转移
设从第 (i) 个油站到下一个油站需要消耗
[ a_i ]
升油，第 (i) 个油站的油价为 (p_i)。
进入第 (i) 个油站时有 (q) 升油，购买一些油以后油箱中有 (r) 升油，必须满足：
[ q\le r\le C ]
并且至少要能开到下一个油站：
[ r\ge a_i ]
到达下一个油站后剩余的油量为
[ r-a_i ]
因此有
[ V_i(q)= \min{(r-q)p_i+V_{i+1}(r-a_i)} ]
其中
[ \max(q,a_i)\le r\le C ]
这就是动态规划的核心转移。
3.3 连续状态如何表示
直接枚举 (q) 不可行，因为 (q) 是连续实数。
可以证明 (V_i(q)) 是一个连续、凸的分段一次函数。
例如，如果后面没有更便宜的油站，那么多买油只会按当前油价线性增加成本，函数的一段斜率就是 (-p_i)。
因此不需要保存所有实数，只需要保存：
- 函数在 (q=0) 处的值；
- 每一段的长度；
- 每一段的斜率。
因为函数是凸函数，斜率从左到右单调不降。
3.4 转移的几何意义
令
[ z=r-a_i ]
则
[ V_i(q)=-p_iq+ \min_{z\ge \max(0,q-a_i)} \left(V_{i+1}(z)+p_i(z+a_i)\right) ]
考虑函数
[ U(z)=V_{i+1}(z)+p_i z ]
它是凸函数，存在一个最小值位置 (t)。这个位置就是斜率第一次满足
[ V'_{i+1}(z)+p_i\ge 0 ]
的地方。
于是：
- 当 (q\le a_i+t) 时，从当前油站买油直到目标油量 (a_i+t)，价值函数的斜率为 (-p_i)；
- 当 (q>a_i+t) 时，不需要再在当前油站买油，直接开到下一个站，价值函数相当于把 (V_{i+1}) 向右平移 (a_i)。
按照这个规则维护分段函数，就可以从终点倒推回起点。
最后，起点出发时油箱为空，所以答案是
[ V_0(0) ]
3.5 正确性
- 状态转移枚举了在当前油站所有可能的购买量，因此不会遗漏任何方案；
- 对于每种到达下一个油站的剩余油量，都取最小花费；
- 分段函数保存了所有斜率变化点，并精确表示连续油量，因此没有离散化误差；
- 从终点向起点归纳，每一步都得到最优值，所以最终得到全局最小费用。
3.6 复杂度
每个价值函数的分段数最多为 (O(N))，处理一个油站需要 (O(N))。
因此：
- 时间复杂度：(O(N^2))；
- 空间复杂度：(O(N))。
四、易错点
距离和油量不能直接相加
两点的距离是千米，油箱容量是升。每段路消耗的油量必须除以 (L)。
最后一段也必须检查容量
即使前面的油站都能到达，最后从某个油站到终点的距离也可能超过一箱油能够行驶的距离。
只检查相邻油站是否可达
如果任意相邻两个需要停靠的位置之间消耗的油量都大于 (C)，就无解。
浮点数比较
输入是实数，判断能否到达和比较油价时应加入足够小的误差，例如
1e-9。油站顺序
题目通常按距离给出油站，但代码先排序更稳妥；同一位置有多个油站时，只保留价格最低的一个。
五、样例验证
输入：
text
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2输出：
text
26.95两种实现均得到 26.95。